Cardinal
In set theory, the cardinal numbers (or just cardinals) are equivalence classes defined by the relation "there exists a bijection from set \(A\) onto set \(B\)".This definition is not really a desired one when working in formal set theory, because these equivalence aren't sets themselves (they are so called proper classes). This can be fixed by using so called . Whereas ordinal numbers may be thought of as "structures" of certain kinds of sets, cardinals are best described as the "sizes" of sets. Introduction The intuitive idea of size works well enough for finite sets, but in the infinite realm it begins to break down. For an example, let's compare the sizes of four sets: the rational numbers, the natural numbers, the even natural numbers, and the real numbers. How do their sizes compare to each other? Most people will give one of two answers. One could argue the following: "The four sets all nest inside each other in this order: even natural numbers, natural numbers, rational numbers, real numbers. A set always has less elements than a superset, so their sizes are in this order from smallest to largest." Someone else would argue, "Since all the sets are infinite, they can't be different sizes — otherwise \(\infty < \infty\). So they're all the same size." These two arguments, seemingly both logical, give us contradictory answers, showing that we need something better than such intuitive reasoning. Instead of asking when one set is smaller than another, we can ask a potentially easier question: when do two sets have the same size? The answer, agreed upon by set theorists, is in the idea of a bijection, also known as a one-to-one correspondence. The latter name suggests a nice visual description of a bijection — pairing up two sets of objects so that no object is left over and every object belongs to only one pair. If there exists a bijection between two sets \(A\) and \(B\), then we say that they have the same cardinality, or that they are equipotent, equinumerous, or sometimes equicardinal. We then denote cardinality of a set \(A\) by \(|A|\). We can also speak of inequalities between sizes of two sets - since naturally we would expect all subsets \(B\) of a set \(A\) to have the size at most that of \(A\), it's natural to define notion "set \(C\) having the size at most the size of \(A\)" as "\(C\) is equinumerous to some subset of \(A\)". Cardinality is simple for finite sets — it's just the number of elements in the set. The empty set has zero cardinality, the set of horns on your pet unicorn has cardinality 1, etc. The bijection definition also works intuitively. You can determine whether two groups of people are the same size by repeatedly removing two at a time, one from each group. This may seem roundabout when we can count all the elements, but what if we can't? A simple example of an infinite set is the set of all nonnegative integers \(\{0,1,2,\ldots\}\). This has a cardinality we call aleph-zero or aleph-null or aleph-naught, notated \(\aleph_0\). Let's try to answer a question comparing the cardinalities of two infinite sets, \(A = \{0,1,2,\ldots\}\) and \(B = \{1,2,3,\ldots\}\). To check for equicardinality, we look for a way to pair off elements with no leftovers or overlaps. Finding a bijection is easy: for each element in \(A\), add one to it and it matches up with an element in \(B\)! So \(A\) and \(B\) have the same cardinality, and \(\{1,2,3,\ldots\}\) has cardinality \(\aleph_0\). Since we took one element away to get from \(A\) to \(B\), this means that \(\aleph_0 - 1 = \aleph_0\), and the opposite argument shows that \(\aleph_0 + 1 = \aleph_0\). In fact, for all finite \(n\), adding or taking away \(n\) elements from an infinite set doesn't change its size. What about \(A = \{0,1,2,\ldots\}\) and \(C = \{0,2,4,6,\ldots\}\)? We simply use the mapping \(x \mapsto 2x\), and that gives us a bijection from \(A\) onto \(C\). So the nonnegative integers have the same cardinality \(\aleph_0\) as just the even ones. So \(\aleph_0 = 2\aleph_0\). This may be a little surprising to people who thought that a set is always larger than each of its proper subsets! Same goes for the set of multiples of 3, multiples of 4, perfect squares, etc. The last of these is especially interesting, because perfect square numbers become more and more sparse when we go on, and their among natural numbers is, in fact, 0. A slightly more complicated mapping allows us to show that the integers \(\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}\) also have cardinality \(\aleph_0\). One bijection involves alternating between the positive and negative integers: 0, 1, -1, 2, -2, ... and it works just like the argument for the even integers. The rational numbers are even trickier, but it is possible to show that they also have cardinality \(\aleph_0\), and that \(\aleph_0^2 = \aleph_0\). Real numbers At this point, it's tempting to conclude that all infinite sets have cardinality \(\aleph_0\). But German mathematician proved that this is not the case. As it turns out, the set of real numbers is so large that there is no bijection from \(\mathbb{N}\) onto \(\mathbb{R}\), so they do not have cardinality \(\aleph_0\). In other words, there are different sizes of infinities! First thing to note is, if we will show that some subset of real numbers has more elements than \(\mathbb{N}\), then the same will follow for all real numbers (because set of real numbers certainly doesn't have less elements than its subset). We will provide a basic outline of Cantor's famous diagonalization proof. We can encode all the real numbers in \((0, 1)\) using their binary expansions, such as 0.0110101101011... Using proof by contradiction, we assume that we can find a bijection from the natural numbers onto \((0,1)\). Then we can make a numbered list of all the real numbers in some order like this (this is, of course, just one example of such ordering, but it should get clear later that this works for any supposed ordering): :1. 0.010110101011110... :2. 0.101010011011100... :3. 0.011100101110101... :4. 0.010101101010000... :5. 0.011100100101011... :6. 0.111010101101000... :... This list supposedly has all the real numbers, but it turns out we can always come up with a real number that isn't on the list! Just take all the bolded numbers: :1. 0.0'10110101011110... :2. 0.1'0'1010011011100... :3. 0.01'1'100101110101... :4. 0.010'1'01101010000... :5. 0.0111'0'0100101011... :6. 0.11101'0'101101000... :... and assemble them into a new real number 0.001100... Then flip all the bits in this number to form a new one, 0.110011... Since it has a different first bit than real number #1, it's not equal to the first. Since it has a different second bit than number #2, it's not equal to the second. Since it has a different third bit than #3, it's not equal to the third, and so on. So our real number isn't on the list at all, even though we assumed ''every real number is there! This is a contradiction, and therefore \((0,1)\) has a different cardinality than the natural numbers. We can show that there is at least as many reals as natural numbers, e.g. by noting that the set \(\{0.1,0.01,0.0001,...\}\) is fully contained in \((0,1)\), and has the same number of elements as \(\mathbb{N}\). More detailed and rigorous statements of this proof can be found all over the Internet, so if you're concerned about details be sure to check those. (For example, we glossed over duplicate expansions such as 0.001011111... = 0.00110000... but these ultimately don't have any effect.) One thing that is worth pointing out is that the real numbers in the interval \((0, 1)\) have, in fact, the same cardinality as the entire set of real numbers — in set theory, a line segment has the same size as a line. There are quite a few bijections for this, one familiar one being the function \(\tan(x)\) which maps \((-\pi/2,\pi/2)\) onto \(\mathbb{R}\). (Don't worry about the fact that it's \((-\pi/2,\pi/2)\) and not \((0, 1)\), the scaling and translating doesn't affect the cardinality.) How many real numbers are there then? One way to symbolize their cardinality is "\(2^{\aleph_0}\)" — each real number is defined by \(\aleph_0\) bits, and there are two choices for each bit. Another symbol is \(\mathfrak{c}\), which is the initial for the name of the cardinal: the '''cardinality of the continuum (or just continuum). Another set with cardinality equal to \(2^{\aleph_0}\) is the power set of the natural numbers, which consists of all sets of natural numbers, finite and infinite. There is a very straightforward mapping from the real numbers onto these sets — a one a position n'' means that ''n is in the set. So 0.111 represents the set {1,2,3}, 0.01010101... the even numbers, etc. Continuum hypothesis So far we have a nice collection of cardinals going: in increasing order, we have the finite cardinalities 0, 1, 2, 3, ... and two infinite cardinalities \(\aleph_0\) and \(2^{\aleph_0}\). Above we (sort of) showed that \(2^{\aleph_0} > \aleph_0\), but our argument doesn't tell us anything about whether there are cardinals between \(\aleph_0\) and \(2^{\aleph_0}\). Intuitively it seems odd that there would be any sets of cardinality between the natural numbers and real numbers, but intuition isn't an ideal way to argue about this. The continuum hypothesis asks the question :Are there any cardinals \(\alpha\) such that \(\aleph_0 < \alpha < 2^{\aleph_0}\)? In a set-theoretic framework known as ZFC, we also know that there is a smallest cardinal greater than \(\aleph_0\).This fact, while it might sound obvious, is actually quite difficult to prove, as there is absolutely no reason why there should exist a smallest cardinal greater than given one. A lot of intuitively clear facts about finite numbers become very hard to show when moving to infinite set theory. We call it \(\aleph_1\), or aleph-one. Thus in ZFC, the continuum hypothesis is equivalent to asking whether \(2^{\aleph_0} = \aleph_1\). The resolution of continuum hypothesis is very interesting and weird. Kurt Gödel showed that it's not possible to disprove it in ZFC - which made many mathematicians of the time believe that it can be proven - but Paul Cohen later showed that it's not possible to prove it either. Thus it's independent of ZFC. In other words, it's neither true nor false, and ZFC just can't "make up its mind". If this is confusing to you, maybe check out our ZFC article for more details on formal theories and independence. In spite of this undecided nature of the continuum, some poorly written introductions to set theory will explicitly or implicitly state that the real numbers have cardinality \(\aleph_1\) by definition. If you've learned this from such a tutorial, unlearn it! Even if you ever use the equality between these two cardinals, you should be aware that they are defined in significantly different way, and that this equality cannot be proven on the grounds of common set theory. More cardinals The of the real numbers has cardinality \(2^{2^{\aleph_0}}\), and the power set of that set has cardinality \(2^{2^{2^{\aleph_0}}}\). Starting to notice a pattern? We already know from Cantor's diagonalization proof that \(2^{\aleph_0} > \aleph_0\). Similar arguments can be made to prove that \(2^{2^{\aleph_0}} > 2^{\aleph_0}\), and \(2^{2^{2^{\aleph_0}}} > 2^{2^{\aleph_0}}\), and so on. In general, Cantor's theorem tells us that for every cardinal \(\alpha\), \(2^\alpha > \alpha\). That is, every set is outnumbered by its power set. From this we see that there is no such thing as the largest cardinal number - for any supposed such cardinal, we could just take its power set, and we would know that it's larger. By the way, there's a more concise standard notation for cardinals like \(2^{2^{\aleph_0}}\) and \(2^{2^{2^{\aleph_0}}}\), called the beth numbers. They are defined as \(\beth_0 = \aleph_0\), \(\beth_1 = 2^{\aleph_0}\), \(\beth_2 = 2^{2^{\aleph_0}}\), \(\beth_3 = 2^{2^{2^{\aleph_0}}}\), etc. Using the beth numbers, we can restate the continuum hypothesis as \(\aleph_1 = \beth_1\), assuming ZFC. There are also the aleph numbers, one of which you're familiar with by now — \(\aleph_0\). Recall that \(\aleph_1\) is defined as the smallest cardinal greater than \(\aleph_0\). Similarly, \(\aleph_2\) is the smallest cardinal greater than \(\aleph_1\), and so forth. The difference between these two sequences is quite important: the beth numbers are created by repeated application of power sets, and the aleph numbers try to make themselves as close together as possible. Oh, and here's some more terminology. \(\aleph_0\) is the smallest infinite cardinal, and as such we define an infinite cardinal as any cardinal at least \(\aleph_0\). Sets with cardinality \(\leq \aleph_0\) are called countable, and sets with cardinality \(> \aleph_0\) are called uncountable. Sets with cardinality \(\aleph_0\) are unsurprisingly called countably infinite. Cardinal arithmetic and ordinals Before we introduce even more cardinals, now's a good time to step back and discuss some theory. * Cardinal ordering. Earlier on, we wrote \(2^{\alpha_0} > \alpha_0\) but we didn't define what \(>\) means. We say that \(\alpha \geq \beta\) iff there are sets \(|A| = \alpha,\, |B| = \beta\) and \(A \supseteq B\). We say that \(\alpha > \beta\) iff \(\alpha \geq \beta\) and \(\alpha \neq \beta\). * Cardinal addition. \(\alpha + \beta\) means taking two disjoint sets \(A\) and \(B\), where \(A\) has cardinality \(\alpha\) and \(B\) has cardinality \(\beta\), and returning the cardinality of their union \(A \cup B\). It's worth noting that we get the same value of \(\alpha+\beta\) no matter what sets \(A\) and \(B\) we choose, as long as they have correct cardinalities. * Cardinal multiplication. If we take cardinals \(\alpha,\beta\) and sets \(A,B\) of these respective cardinalities, then we define \(\alpha\cdot\beta\) to be the cardinality of the \(A\times B\). Intuitively, this means that we take are taking \(|B|\) copies of \(A\) and we are taking their collective size. * Cardinal exponentiation. To exponentiate cardinals, we first need a notion of "set exponentiation" (just like disjoint union and Cartesian product are "set addition" and "set multiplication"). This is achieved by, again given two sets \(A,B\), considering the set of all functions from \(B\) to \(A\). This set is denoted by \(A^B\) (or sometimes \(^BA\)). We then define cardinal exponentiation to be an operation taking cardinalities of sets \(A,B\) and returning the cardinality of set \(A^B\). A justification for this definition is as follows: when we are constructing a function from \(B\) to \(A\), then for every element of \(B\) we can independently choose any of \(|A|\) elements of \(A\), thus, to count how many functions from \(B\) to \(A\) there are, we would want to multiply \(|A|\) with itself \(|B|\) times. * Infinite cardinal sums. Given a countably infinite sequence of cardinals \(\alpha_1, \alpha_2, \alpha_3, \ldots\), we define their sum \(\sum_i \alpha_i\) as the infinite union \(\bigcup_i A_i\) where each \(A_i\) has cardinality \(\alpha_i\), and all \(A_i\) are mutually disjoint. Now that we have some fundamentals out of the way, let's talk about the relationship between cardinals and ordinals. Cardinals are closely related to the system of ordinal numbers, but they're not the same. Their arithmetic systems behave differently — for example, \(\omega + 1 \neq \omega\) while \(\aleph_0 + 1 = \aleph_0\). From here on we use the Von Neumann definition of ordinals. \(\omega\), as we've established, is the smallest infinite ordinal. \(\omega_1\) is the name for the smallest uncountable ordinal, \(\omega_2\) for the smallest ordinal of cardinality \(\aleph_2\), and so forth. It's convenient to "define" a cardinal number as equal to the smallest ordinal number with its own cardinality. So we'd say that \(\omega = \aleph_0\), \(\omega_1 = \aleph_1\), and so forth, which is nice because now the cardinal numbers are represented by actual sets. How can this be reasonable if \(\omega + 1\) and \(\aleph_0 + 1\) are different? That's because we're using different definitions of addition here, and ordinal addition is defined differently from cardinal addition. Distinguishing between the two is just a matter of context, and it's rarely if ever ambiguous. With all this in mind, we have enough foundation to move on to larger cardinal numbers. Higher cardinals Using the infinite sum definition, we can create a new, larger cardinal \(\aleph_0 + \aleph_1 + \aleph_2 + \cdots\). This is necessarily larger than all of the summands, and we'll call it \(\aleph_\omega\). \(\aleph_{\omega + 1}\) doesn't require much explanation — it's the next cardinal after \(\aleph_\omega\). More generally, we can consider the aleph hierarchy, which is a hierarchy of cardinal numbers indexed by all ordinal numbers. It is defined as follows: \(\aleph_0\) is, as before, cardinality of set \(\{0,1,2,...\}\). If we have cardinal \(\aleph_\alpha\) defined, then \(\aleph_{\alpha+1}\) is defined as the smallest cardinal greater than \(\aleph_\alpha\). Finally, if \(\alpha\) is a limit ordinal, then we have \(\aleph_\beta\) defined for all \(\beta<\alpha\), then we define \(\aleph_\alpha\) as the sum \(\sum_{\beta<\alpha}\aleph_\beta\). Similarly we can define the beth hierarchy, as \(\beth_0=\aleph_0\), \(\beth_{\alpha+1}=2^{\beth_\alpha}\) and for limit \(\alpha\), \(\beth_\alpha=\sum_{\beta<\alpha}\aleph_\beta\). The generalized continuum hypothesis (GCH) asks whether, for all ordinals \(\alpha\), \(\beth_\alpha = \aleph_\alpha\). Like the continuum hypothesis, GCH is independent of ZFC. Since \(\aleph_0 = \omega\), we can write \(\aleph_\omega = \aleph_{\aleph_0}\), and we can keep iterating the map \(\alpha \mapsto \aleph_\alpha\) to get \(\aleph_{\aleph_{\aleph_0}}, \aleph_{\aleph_{\aleph_{\aleph_0}}}, \ldots\). Just like how we used an infinite sum to reach \(\aleph_\omega\), we can sum these all together to get a cardinal visualized as \(\aleph_{\aleph_{\aleph_{._{._.}}}}\). As an ordinal, this looks like \(\omega_{\omega_{\omega_{._{._.}}}}\) and we call it the (first) omega fixed point. Similarly there is \(\beth_{\beth_{\beth_{._{._.}}}}\). This isn't the limit of cardinal notation, by the way — we can also consider sums such as \(\aleph_1 + \aleph_{\aleph_1} + \aleph_{\aleph_{\aleph_1}} + \cdots\), which is also an aleph fixed point. From these hierarchies we can define some new terms. A successor cardinal is a cardinal that immediately follows another. \(1,2,3,4,\ldots\) are all successor cardinals, but the ones we care about are of the form \(\aleph_{\alpha + 1}\) for some ordinal \(\alpha\). It turns out that all infinite successor cardinals are regular. We've already seen that \(\aleph_1\) is regular, and so are \(\aleph_2\) and \(\aleph_3\) and \(\aleph_{\omega + 1}\). The weak limit cardinals are the cardinals that are neither successor cardinals nor 0. Examples are \(\aleph_0\), \(\aleph_\omega\), and the first aleph fixed point. The strong limit cardinals are \(\beth_\alpha\) where \(\alpha\) is zero or a limit ordinal. Cofinality Notice how \(\aleph_\omega\) is expressible as a countably infinite sum of smaller cardinals \(\aleph_0 + \aleph_1 + \aleph_2 + \cdots\). The same goes for the familiar \(\aleph_0\) — it's equal to \(0 + 1 + 2 + 3 + \cdots\).And no, I don't care whether you watched the Numberphile video, you can't use Ramanujan summation to make this "equal" to \(-1/12\). This is set theory, not complex analysis. Same goes for the first aleph fixed point \(\aleph_{\aleph_{\aleph_{._{._.}}}} = \aleph_0 + \aleph_{\aleph_0} + \aleph_{\aleph_{\aleph_0}} + \cdots\). But \(\aleph_1\) cannot be expressed in this way. We can try summing \(\aleph_0\) copies of \(\aleph_0\), but \(\aleph_0 + \aleph_0 + \aleph_0 + \cdots = \aleph_0\). We have to add uncountably many \(\aleph_0\)'s to get to \(\aleph_1\) — in fact, we have to add \(\aleph_1\) of them. Any sum of smaller cardinals that equals \(\aleph_1\) has to have at least \(\aleph_1\) summands. Intuitively, \(\aleph_1\) can't be broken into a smaller number of smaller parts. We define the cofinality of a cardinal \(\alpha\) as the least cardinality of a set of ordinals less than \(\alpha\) that sums to \(\alpha\). That is, it is the minimal number of "smaller parts" necessary to create \(\alpha\). So \(\aleph_0\), \(\aleph_\omega\), and the first aleph fixed point have cofinality \(\aleph_0\). \(\aleph_1\) has cofinality \(\aleph_1\). A cardinal is regular iff it is equal to its own cofinality (i.e. it cannot be broken into a smaller number of smaller parts), or singular otherwise. Let's classify some infinite cardinals as singular or regular: * \(\aleph_0\) is regular. You can't add finitely many natural numbers to get an infinite cardinal. * \(\aleph_1\) is regular. You can't add countably many countable cardinals to get an uncountable cardinal. * \(\aleph_2\) is regular. * \(\aleph_\omega\) is singular — just sum all the smaller cardinals, of which there are \(\aleph_0\). * \(\aleph_{\omega + 1}\) is regular. * \(\aleph_{\omega + 2}\) is regular. * \(\aleph_{\omega 2}\) is singular. * \(\aleph_{\omega 2 + 1}\) is regular. * \(\aleph_{\aleph_0}\) is singular. (It's the sum of all previous aleph numbers, which have cardinality \(\aleph_0\).) * The first aleph fixed point is singular. (Recalling the infinite sum we used to construct it, it has cofinality \(\omega\).) A pattern emerges — all the weak limit cardinals other than \(\aleph_0\) are singular, and all the successor cardinals are regular. Is this always true? Are there any uncountable regular weak limit cardinals? Inaccessible cardinals The answer is "maybe." The statement is actually independent of ZFC. Set theorists refer to uncountable regular weak limit cardinals as weakly inaccessible cardinals. Notes See also Category:Set theory Category:Transfinite ordinals